package com.yiwenup.leetcode.offer;

/**
 * https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/
 **/
public class No029 {

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了97.46%的用户
     * 内存消耗：39.6 MB, 在所有 Java 提交中击败了69.87%的用户
     */
    public int[] spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new int[0];

        int row = matrix.length;
        int column = matrix[0].length;

        int top = 0;
        int bottom = row - 1;
        int left = 0;
        int right = column - 1;
        int idx = 0;
        int[] res = new int[row * column];

        while (left <= right && top <= bottom) {
            for (int i = left; i <= right; i++) {
                res[idx++] = matrix[top][i];
            }
            for (int i = top + 1; i <= bottom; i++) {
                res[idx++] = matrix[i][right];
            }
            if (left < right && top < bottom) {
                for (int i = right - 1; i > left; i--) {
                    res[idx++] = matrix[bottom][i];
                }
                for (int i = bottom; i > top; i--) {
                    res[idx++] = matrix[i][left];
                }
            }

            left++;
            right--;
            top++;
            bottom--;
        }

        return res;
    }
}
